def max_subarray_sum(arr):
    """
    找出整数数组中子数组之和的最大值
    使用Kadane算法
    """
    if not arr:
        return 0
    
    max_so_far = arr[0]
    max_ending_here = arr[0]
    
    for i in range(1, len(arr)):
        # 当前元素单独，或者加上前面的子数组
        max_ending_here = max(arr[i], max_ending_here + arr[i])
        # 更新全局最大值
        max_so_far = max(max_so_far, max_ending_here)
    
    return max_so_far

# 测试用例
def test_max_subarray():
    test_cases = [
        ([1, -2, 3, 5, -1], 8),
        ([1, -2, 3, -8, 5, 1], 6),
        ([1, -2, 3, -2, 5, 1], 7),
        ([-1, -2, -3], -1),  # 全负数情况
        ([], 0)  # 空数组
    ]
    
    print("=== 最大子数组和测试 ===")
    for i, (arr, expected) in enumerate(test_cases, 1):
        result = max_subarray_sum(arr)
        status = "✓" if result == expected else "✗"
        print(f"测试 {i}: {arr} -> 结果: {result}, 期望: {expected} {status}")

if __name__ == "__main__":
    test_max_subarray()